//给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 *
// 。 
//
// 示例 1: 
//
// 输入: "2-1-1"
//输出: [0, 2]
//解释: 
//((2-1)-1) = 0 
//(2-(1-1)) = 2 
//
// 示例 2: 
//
// 输入: "2*3-4*5"
//输出: [-34, -14, -10, -10, 10]
//解释: 
//(2*(3-(4*5))) = -34 
//((2*3)-(4*5)) = -14 
//((2*(3-4))*5) = -10 
//(2*((3-4)*5)) = -10 
//(((2*3)-4)*5) = 10 
// Related Topics 递归 记忆化搜索 数学 字符串 动态规划 
// 👍 467 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class DifferentWaysToAddParentheses {
    public static void main(String[] args) {
        new DifferentWaysToAddParentheses().new Solution().diffWaysToCompute("2-1-1");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 这道题目本身是用的分治的思想，但是实现的方式是通过递归时间的
         * 分治算法：是我看了不知道怎么写的题目了
         * 对于一个形如 x op y（op 为运算符，x 和 y 为数） 的算式而言
         * 它的结果组合取决于 x 和 y 的结果组合数，而 x 和 y 又可以写成形如 x op y 的算式。
         *
         * 因此，该问题的子问题就是 x op y 中的 x 和 y：以运算符分隔的左右两侧算式解！！！
         *
         * 然后我们来进行 分治算法三步走：
         *  分解：按运算符分成左右两部分，分别求解
         *  解决：实现一个递归函数，输入算式，返回算式解
         *  合并：根据运算符合并左右两部分的解，得出最终解（所有可能的计算结果）
         */
        public List<Integer> diffWaysToCompute(String expression) {
            List<Integer> list = new ArrayList<>();
            int len = expression.length();
            int start;// 第一个运算符的位置
            for (start = 0; start < len; start++){
                if (!Character.isDigit(expression.charAt(start))) break;
            }
            //全是数字直接返回其实就行，不在这里返回的话也进不去循环
            if (start == len) {
                list.add(Integer.parseInt(expression));
                return list;
            }

            for (int i = start; i <len ; i++) {//这个循环就保证了所有的计算情况都会发生
                if (Character.isDigit(expression.charAt(i))) continue;//找运算符
                char op = expression.charAt(i);//找到之后就递归计算
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i+1, len));
                for (int l : left){//合并所有的计算结果
                    for (int r : right){
                        if (op == '+') list.add(l + r);
                        else if (op == '-') list.add(l - r);
                        else list.add(l * r);
                    }
                }
            }
            return list;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}